  IOI. 5 (Rescrieri). Un s-termen este o secventa de caractere 's','(' ,')'
construita recursiv conform regulilor:
s este un s-termen;
Daca , sunt s-termeni, atunci () este un s-termen.
Exemple: ((((ss)(ss))s)s)) sau ((((ss(sss(ss
parantezele drepte putnd fi omise, ele neaducnd informatii noi.
Lungimea unei s-termen este numarul de caractere 's' din el.
    1. Se citeste de la intrare numarul natural n<10. Se cere sa se scrie o
procedura gensterm care sa creeze pentru fiecare k=1,2,..,n un fisier text
care sa contina toti s-termenii de lungime k;
n fisier s-termenii sunt separati prin ';', iar fisierul se ncheie cu '.'.
   Se introduce asupra s-termenilor urmatoarea operatie, numita reducere:
orice s-subtermen avnd forma (((sA)B)C) (unde A,B,C sunt s-subtermeni) poate
fi transformat n ((AC)(BC)) adica:
        (((sA)B)C)  ->  ((AC)(BC)).
   Pentru simplificare vom spune n continuare termen n loc de s-termen.
Pentru un termen dat exista mai multe moduri n care poate fi ales un
subtermen asupra caruia se poate efectua reducerea. Prin normalizarea unui
termen se ntelege aplicarea succesiva a reducerii att timp ct este posibil.
Exemplu de sir de reduceri: ((((ss(sss(ss(((ss((sss(ss
                            ((s(ss(((sss(ss((s(ss((s(ss(s(ss.
   2. Alegeti o structura de date adecvata pentru reprezentarea si reducerea
termenilor. Scrieti doua proceduri readterm si printterm care sa treaca de la
un termen la reprezentarea aleasa si invers.
Demonstrati corectitudinea lor;
   3. Scrieti o procedura reduce care sa efectueze reducerea unui termen
asupra unui subtermen specificat si demonstrati corectitudinea ei;
   4. Scrieti o procedura normalize care, pentru un termen dat, efectueaza
succesiv reduceri pna cnd nu mai este posibil sau pna cnd numarul de
reduceri depaseste 30;
    5. Incorporati cele de mai sus ntr-un program care:
a) Citeste o valoare pentru n;
b) utilizeaza termenii de lungime n generati de genterm;
c) transforma acesti termeni n repezentarea aleasa;
d) i normalizeaza (daca este posibil);
e) afiseaza rezultatul normalizarii;
f) afiseaza numarul de reduceri efectuate pna la normalizare sau
not normalized daca acest numar este 0 sau depaseste 30;
g) afiseaza numarul de termeni de lungime n si numarul de termeni normalizati.
=========================================
Solutia 1 (Mihai Stroe)

    Generarea tuturor s-termenilor de lungime k se realizeaza prin metoda
  backtracking si este sinonima cu generarea sirurilor de 2*k-2 paranteze
  care se inchid corect.
    Pentru reprezentarea s-termenilor se foloseste structura de arbore binar
  strict, in care frunzele contin caracterul 's', iar celelalte noduri
  contin '('. Procedurile READTERM si PRINTTERM realizeaza crearea si
  parcurgerea in preordine a arborelui. Reducerea se realizeaza printr-o
  parcurgere in preordine si transformarea unui subarbore (((sA)B)C), daca
  exista, in subarborele ((AC)(BC)); se foloseste subrutina COPYTREE pentru
  a obtine doi subarbori C. Normalizarea este o repetare de reduceri, iar
  celelalte cerinte sunt banale.

uses crt;
type ref=^nod;
     nod=record
           info:char;
           st,dr:ref;
         end;

var fi,fo:text;
    i,j,k,l,m,n,nr,num,norm:longint;
    s:string;
    rad,p,p1,p2:ref;
    st:array[1..30]of byte;
    c:char;

procedure deltree(var p:ref);
begin
  if p=nil then exit;
  deltree(p^.st);
  deltree(p^.dr);
  dispose(p);
end;

procedure gensterm(n:longint);
var k,np,ns:longint;
  function valid:boolean;
    begin
      if st[k]=1 then inc(np)else inc(ns);
      valid:=true;
      if ((np<ns)and(k<>2*n-1))or((ns-np<>1)and(k=2*n-1))then valid:=false;
      if np>n-1 then valid:=false;
      if st[k]=1 then dec(np)else dec(ns);
    end;
  procedure tipar;
    begin
      for i:=1 to 2*n-1 do
          if st[i]=1 then write(fo,'(')
                     else write(fo,'s');
      writeln(fo);
      inc(nr);
    end;
begin
  write('Input file name for terms of the length ',n,' ');
  readln(s);
  assign(fo,s);
  rewrite(fo);
  fillchar(st,sizeof(st),0);
  nr:=0;
  k:=1;
  np:=0;
  ns:=0;
  while k>0 do
    begin
      repeat inc(st[k]);until(st[k]>2)or((st[k]<=2)and valid);
      if st[k]>2 then
         begin
           st[k]:=0;
           dec(k);
           if st[k]=1 then dec(np)
                      else dec(ns);
         end
         else
         begin
             if k<>2*n-1 then
                if st[k]=1 then inc(np)
                           else inc(ns);
             if k=2*n-1 then tipar
                        else inc(k);
         end;
    end;
  close(fo);
end;

procedure printterm;forward;
procedure reduce(p:ref);
procedure copytree(source:ref;var dest:ref);
begin
  if source=nil then begin dest:=nil;exit;end;
  dest^.info:=source^.info;
  dest^.st:=nil;
  dest^.dr:=nil;
  if source^.st<>nil then
     begin
       new(dest^.st);
       copytree(source^.st,dest^.st);
     end;
  if source^.dr<>nil then
     begin
       new(dest^.dr);
       copytree(source^.dr,dest^.dr);
     end;
end;

begin
  new(p1);
  new(p2);
  new(p1^.st);new(p1^.dr);new(p2^.st);
  copytree(p^.st^.st^.dr,p1^.st);
  copytree(p^.dr,p1^.dr);
  p1^.info:='(';
  copytree(p^.st^.dr,p2^.st);
  new(p2^.dr);
  copytree(p1^.dr,p2^.dr);
  p2^.info:='(';
  deltree(p^.st);
  deltree(p^.dr);
  new(p^.st);
  new(p^.dr);
  p^.st:=p1;
  p^.dr:=p2;
end;

procedure normalize;
var done,imposible:boolean;
procedure preord(p:ref);
begin
  if p^.info='s' then exit;
  if p=nil then exit;
  if done then exit;
  if p^.st<>nil then
     if p^.st^.st<>nil then
        if p^.st^.st^.st<>nil then
           if p1^.st^.st^.dr<>nil then
           if p^.st^.st^.st^.info='s' then
              begin
                reduce(p);
                done:=true;
              end;
  if done then exit;
  preord(p^.st);
  if done then exit;
  preord(p^.dr);
  if (p=rad)and(not done) then imposible:=true;
end;

begin
  num:=0;
  imposible:=false;
  while (not imposible)and(num<32)do
    begin
      done:=false;
      preord(rad);
      if not imposible then inc(num);
    end;
  if num>30 then num:=0;
end;

procedure readterm(s:string);
procedure preord(p:ref;var s:string);
begin
  if s[1]='s' then
     begin
       p^.info:='s';
       delete(s,1,1);
       p^.st:=nil;
       p^.dr:=nil;
     end
     else
     begin
       new(p^.st);
       new(p^.dr);
       p^.info:='(';
       delete(s,1,1);
       preord(p^.st,s);
       preord(p^.dr,s);
     end;
end;

begin
  new(rad);
  preord(rad,s);
end;

procedure printterm;
procedure pre(var p:ref);
begin
  if p=nil then exit;
  write(p^.info);
  if p^.info='s' then
     begin
       exit;
     end;
  pre(p^.st);
  pre(p^.dr);
end;

begin
  pre(rad);
  writeln;
end;

begin
  {$m 60000,0,600000}
  write('Input n ');
  readln(n);
  if n>=10 then
     begin
       writeln('Wrong entry');
       halt;
     end;
  for k:=1 to n do
      gensterm(k);
  norm:=0;
  reset(fo);
  for i:=1 to nr do
      begin
        readln(fo,s);
        readterm(s);
        printterm;
        normalize;
        if num<>0 then
           begin
             printterm;
             inc(norm);
           end
           else
             writeln('Not normalized');
        deltree(rad);
        if i mod 10=0 then
           begin
             writeln('press a key to continue');
             repeat until keypressed;c:=readkey;
             clrscr;
           end
      end;
  close(fo);
  writeln('There are ',nr,' s-terms of the length ',n);
  writeln('Of those, ',norm,' could be normalized');
  repeat until keypressed;
end.
------------------------------------------
Solutia mea:
Algoritm:
Pentru gensterm se poate da un algoritm recursiv care folosete ca variabile globale n (citit la
intrare), i mulimile L,L':
gensterm(k):
  1. Dac[ k=1 atunci L':={s}; salt la 4
              altfel gensterm(k-1);
  2. L':=H;
  3. Pentru fiecare L
        Pentru i:=1,k-1
       Fie scrierea =sy unde  conine i-1 s-uri;
           L':=L'B{(ssy};
  4. L:=L'; 
     se scrie L n fiierul de iesire TERM_k;
  5. Dac[ k=n atunci Stop altfel Revenire.

              Un s-termen constituie de fapt scrierea infixat[ a unei expresii de tip aritmetic avnd ca
operand s i ca operator (. Cum reprezentarea natural[ a scrierii infixate este aceea prin arbori binari,
putem lua arborii binari ca reprezentare.
              Atunci printterm constituie de fapt parcurgerea infixat[ a unui arbore binar (algoritm
cunoscut din manualul de liceu), iar pentru readterm putem da diveri algoritmi; de exemplu;
readterm()
Intrare: s-termenul ;
ieire: Arborele binar a c[rui parcurgere infixat[ este ;
Iniial T:={s,s,..,s}, num[rul de s-uri fiind egal cu cel din ;
Not[m cu N(x) num[rul de paranteze din expresia x:
1. Pentru i:=1,N()
   1.1. Dac[ N()=0 atunci Stop;
   1.2. Fie =(yzy cu N(yzy)=0 (se pune n eviden[ ultima parantez[);
          T:=(T-{y,z})B{p} unde p este un nume nou dat arborelui 
                                                                       (

                                       y z
           :=py;
2. Se scrie arborele aflat n T.
              O reducere nseamn[ o echilibrare de arbori dup[ regula:

                                                                       (      (

                                       ( C                                                 ((

               (                        B         =>      A                        CB                       C

s                                     A

                         O normalizare const[ n aplicarea ct timp este posibil a urm[torului algoritm:
Fie =(((sABCy unde:
   - A,B,C sunt s-termeni;
   - In ABCy nu exist[ ((( ca subcuvnt;
Atunci,  se nlocuiete cu :=((AC(BCy.

              Ali algoritmi pot fi g[sii prin analiza programului urm[tor sau a programului dat de conf.
dr. Horia Georgescu n GI/2 1991.
Program:
uses crt;
type vector=array[1..10] of byte;
     nod=^celula;
     celula=record
            radacina:char;
            stanga,dreapta:nod;
            end;
var n,i:byte;
    coef:vector;
    ultimul:boolean;
    start,start2:nod;
    s:string[20];
  curent,nr_termeni,nr_normalizari,
      nr_normalizati:integer;
--------------------------------------------------
function height(n:nod):byte;
var r:byte;
    crt:nod;
begin
crt:=n;
r:=0;
while crt^.radacina='(' do
      begin
      inc(r);
      crt:=crt^.stanga;
      end;
height:=r;
end;
---------------------------------------------------procedure printterm(var
n:nod);
begin
s:=s+n^.radacina;
inc(curent);
if n^.radacina='(' then
   begin
   printterm(n^.stanga);
   printterm(n^.dreapta);
   end;
end;
---------------------------------------------------procedure normalize(var
n,na:nod);
var h:byte;
    tmp,crt:nod;
begin
if n^.radacina='(' then
   begin
   normalize(n^.stanga,n);
   normalize(n^.dreapta,n);
   if height(n)=3 then
      begin
      inc(nr_normalizari);
      tmp:=n^.stanga;
      n^.stanga:=n^.stanga^.dreapta;
      n^.stanga^.stanga^.stanga:=
 n^.stanga^.stanga^.dreapta;
      n^.stanga^.stanga^.dreapta:=n^.dreapta;
      tmp^.dreapta:=n;
      if na^.dreapta=n then na^.dreapta:=tmp
      else na^.stanga:=tmp;
      end;
   end;
end;
---------------------------------------------------procedure readterm(var
n:nod);
begin
new(n);
n^.radacina:=s[curent];
inc(curent);
if n^.radacina='(' then
   begin
   readterm(n^.stanga);
   readterm(n^.dreapta);
   end;
end;
---------------------------------------------------procedure
genterm(coef:vector;x:integer);
var i,j:byte;
    gata:boolean;
begin
gata:=true;
for i:=2 to n-1 do if coef[i]<>coef[i-1]+1 then gata:=false;
if gata=true then
   ultimul:=gata;
 if (x<n-1) and (not ultimul) then
   for i:=coef[x] to coef[x]+2 do
       begin
       if not ultimul then
          begin
          coef[x+1]:=i;
          genterm(coef,x+1);
          end;
       end
 else if x=n-1 then
    begin
    s:='';
    for i:=1 to n-2 do
        begin
        s:=s+'(';
        for j:=coef[i] to coef[i+1]-1 do s:=s+'s';
        end;
    s:=s+'(';
    for i:=coef[n-1] to n do s:=s+'s';
    curent:=1;
    write(s,'   ');
    s:='';
    curent:=1;
    readterm(start);
    start2^.stanga:=start;
    nr_normalizari:=0;
    normalize(start,start2);
    printterm(start2^.stanga);
    if nr_normalizari in [30,0] then 
       s:='NOT NORMALIZED'
    else inc(nr_normalizati);
    inc(nr_termeni);
    write(s);
    if not(nr_normalizari in [30,0]) then writeln
 (' normalizat in ',nr_normalizari,' reduceri.')
    else writeln;
    end;
end;
---------------------------------------------------begin
clrscr;
assign(output,'output.io5');
rewrite(output);
readln(n);
ultimul:=false;
for i:=1 to n-1 do coef[i]:=1;
nr_normalizati:=0;
nr_termeni:=0;
genterm(coef,1);
writeln(nr_termeni,' termeni, dintre care ',nr_normalizati,' normalizati.');
end.
------------------------------------------
